package lcr;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class Test0184 {
}

class Checkout {
    Deque<Integer> maxDeque =new LinkedList<>();
    Deque<Integer> deque =new LinkedList<>();
    public Checkout() {

    }

    public int get_max() {
        Integer last = maxDeque.peekLast();
        return last == null ? -1 : last;
    }

    public void add(int value) {
        while (!maxDeque.isEmpty() && maxDeque.peekLast() < value) {
            maxDeque.pollLast();
        }
        maxDeque.offer(value);
        deque.offer(value);
    }

    public int remove() {
        if (deque.isEmpty()) return -1;
        Integer first = deque.poll();
        if (first.equals(maxDeque.peekFirst())) maxDeque.pollFirst();
        return first;
    }
}
